package com.hspedu.newData.面试题;

import com.hspedu.newData.dmsxl.ds.ListNode;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-21 
 * @Version: 1.0
 */

public class 面试题0206回文链表 {

    public boolean isPalindrome(ListNode head) {

        ListNode first = head;
        ListNode second = findMid(head);
        ListNode node2 = second.next;
        second.next = null;
        ListNode reverse = reverse(node2);

        while (reverse!= null){
            if (reverse.val!=first.val){
                return false;
            }
            reverse = reverse.next;
            first = first.next;
        }

        return true;
    }


    public ListNode reverse(ListNode head){
        ListNode cur = null;

        while (head!=null){
            ListNode next = head.next;
            head.next = cur;
            cur = head;
            head = next;
        }

        return cur;
    }

    public ListNode findMid(ListNode head){
        ListNode first = new ListNode(0,head);
        ListNode second = first;

        while (second!=null&&second!=null){
            first = first.next;
            second = second.next.next;
        }


        return first;
    }
}
